#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 021. 合并两个有序链表.py
@time: 2022/1/6 14:05
@desc: https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/
> 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

1. 归并，O(M+N), O(1)
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if not list1 and not list2:
            return None
        if list1 and not list2:
            return list1
        if not list1 and list2:
            return list2
        head = None
        p, q, c = list1, list2, None
        if list1.val <= list2.val: head= c =list1; p = list1.next
        else: head = c = list2; q = list2.next
        while p and q:
            if p.val<=q.val:
                c.next = p
                p = p.next
            else:
                c.next = q
                q = q.next
            c = c.next
        if p:
            c.next = p
        if q:
            c.next = q
        return head

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution02(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if not list1 and not list2:
            return None
        if list1 and not list2: return list1
        if list2 and not list1: return list2
        p, q, dummy = list1, list2, ListNode()
        c = dummy
        while p and q:
            if p.val<=q.val:
                c.next = p
                p = p.next
            else:
                c.next = q
                q = q.next
            c = c.next
        if p: c.next = p
        if q: c.next = q
        return dummy.next
